/**********************************************
* Define the Node in Deque
***/
template <typename T>
class DoubleLinkedNode
{
public:
	DoubleLinkedNode(T Content)
		: pMainField(Content), pNext(0), pPrevious(0) {}
	~DoubleLinkedNode()
	{
		delete pMainField;
	}
	T pMainField;
	DoubleLinkedNode* pPrevious;
	DoubleLinkedNode* pNext;
};

/**********************************************
* Define the data structure of Deque
***/
template <typename T>
class Deque
{
public:
	Deque();
	virtual ~Deque();
	void Clear();
	void Serve();
	void Append(T Elem);
	bool IsEmpty() const {return (iCount==0);}
protected:
	enum {MAX_ITEM = 50};
	int iCount;
	DoubleLinkedNode<T>* pFront;
	DoubleLinkedNode<T>* pRear;
};


template <typename T>
Deque<T>::Deque()
{
	pFront = 0;
	pRear = 0;
	iCount = 0;
}

template <typename T>
Deque<T>::~Deque()
{
	Clear();
}

template <typename T>
void Deque<T>::Clear()
{
	while(!IsEmpty())	// Clear the Deque
	{
		Serve();
	}
	pFront = 0;
	pRear = 0;
}


template <typename T>
void Deque<T>::Append(T Elem)
{
	if (iCount >= MAX_ITEM)
	{
		return;
	}
	DoubleLinkedNode<T>* pNewItem = new DoubleLinkedNode<T>(Elem);
	if(iCount == 0)			// if Deque is empty
	{
		pFront = pNewItem;
	}
	else
	{
		pRear->pNext = pNewItem;
		pNewItem->pPrevious = pRear;
	}
	pRear = pNewItem;
	iCount++;
}

template <typename T>
void Deque<T>::Serve()
{
	if(iCount == 0)
	{
		return;
	}	
	if(pFront == pRear)		//The only one element is being served
	{
		pRear = 0;
	}
	DoubleLinkedNode<T>* pElemToDel = pFront;
	if (pFront->pNext != 0)
	{
		pFront -> pNext -> pPrevious = 0;
	}
	pFront = pFront->pNext;
	delete pElemToDel;
	pElemToDel = 0;
	iCount --;
}